package com.myc.subjects.binarytreeandrecurtion;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * LeetCode题号：110
 *
 * 平衡二叉树
 *
 * 给定一个二叉树，判断它是否是高度平衡的二叉树。
 * 本题中，一棵高度平衡二叉树定义为：
 * 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
 *
 * 示例 1：
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：true
 *
 * 示例 2：
 * 输入：root = [1,2,2,3,3,null,null,4,4]
 * 输出：false
 *
 * 示例 3：
 * 输入：root = []
 * 输出：true
 *
 * 提示：
 * 树中的节点数在范围 [0, 5000] 内
 * -104 <= Node.val <= 104
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/balanced-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Pinghengerchashu {

    /*
                1
             2     2
          3    3
        4  4
     */
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode21 = new TreeNode(1);
        TreeNode treeNode22 = new TreeNode(1);
        TreeNode treeNode31 = new TreeNode(1);
        TreeNode treeNode32 = new TreeNode(1);
        TreeNode treeNode41 = new TreeNode(1);
        TreeNode treeNode42 = new TreeNode(1);

        treeNode1.left = treeNode21;
        treeNode1.right = treeNode22;
        treeNode21.left = treeNode31;
        treeNode21.right = treeNode32;
        treeNode31.left = treeNode41;
        treeNode31.left = treeNode42;

        Pinghengerchashu p = new Pinghengerchashu();
        System.out.println(p.isBalanced2(treeNode1));
    }

    /**
     * 方法一：先序遍历
     * 时间复杂度：O(n * log^n)
     * 对于每个节点而言，满足平衡二叉树的的条件有：
     * 1.当前节点是平衡二叉树（左右子树的高度之差小于等于1）
     * 2.左右子树均为平衡二叉树
     * 我们使用先序遍历时，需要计算子树的高度。
     */
    public boolean isBalanced1(TreeNode root) {
        //边界条件：空节点是平衡二叉树
        if(root == null) return true;

        //先通过计算左右子树的高度，判断当前节点是够满足平衡二叉树的要求
        int leftheight = getTreeHeight1(root.left);
        int rightheight = getTreeHeight1(root.right);
        boolean isCurrBalanced = Math.abs(leftheight - rightheight) > 1 ? false : true;

        //同时满足左右子树和当前节点都是平衡二叉树，则返回true
        return isCurrBalanced && isBalanced1(root.left) && isBalanced1(root.right);

    }

    //递归计算树高度的方法
    public int getTreeHeight1(TreeNode root){
        //空节点高度为0，退出递归条件
        if(root == null) return 0;
        int leftHeight = getTreeHeight1(root.left);
        int rightHeight = getTreeHeight1(root.right);

        //左右子树的高度的最大值 + 1
        return Math.max(leftHeight, rightHeight) + 1;
    }

    /**
     * 方法二：后续遍历
     * 时间复杂度：O(n)
     * 先序遍历的缺点是：每次自顶向下遍历时，都会重复自底向上计算其子节点的树的高度，导致冗余。
     * 后序遍历在计算树的高度的同时，判断是否为平衡二叉树,并返回
     */

    public boolean isBalanced2(TreeNode root) {
        //等于0表示空树，大于0表示平二叉树，等于 -1 表示非平衡二叉树
        return getTreeHeight2(root) >= 0;
    }

    //计算树高度的方法，非平衡二叉树直接返回 -1
    public int getTreeHeight2(TreeNode root){
        //空树返回0，退出递归条件
        if(root == null) return 0;

        //递归计算左右子树高度
        int leftHeight = getTreeHeight2(root.left);
        int rightHeight = getTreeHeight2(root.right);

        //平衡二叉树返回高度，非平衡二叉树返回 -1
        if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) return Math.max(leftHeight, rightHeight) + 1;
        else return -1;
    }

    //官方题解
    //方法一：自顶向下的递归
    public boolean isBalancedOfficial1(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(heightOfficial1(root.left) - heightOfficial1(root.right)) <= 1 && isBalancedOfficial1(root.left) && isBalancedOfficial1(root.right);
        }
    }

    public int heightOfficial1(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(heightOfficial1(root.left), heightOfficial1(root.right)) + 1;
        }
    }

    //方法二：自底向上的递归
    public boolean isBalancedOfficial2(TreeNode root) {
        return heightOfficial2(root) >= 0;
    }

    public int heightOfficial2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = heightOfficial2(root.left);
        int rightHeight = heightOfficial2(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

/**
 * 总结：
 * 1.在需要计算树高的递归调用中，后序遍历比先序遍历更具备优势，因为计算树高必须自底向上递归。
 * 2.合理利用int类型返回值来处理特殊情况，这一题树高都是正整数，那么负数就可以被利用起来表示特殊结果
 */